#include <iostream>
#include <vector>
#include <stack>
using namespace std;


void quilkSort(vector<int>& vecArr){
	
	int n=vecArr.size();
	stack<pair<int,int>> st;
	st.push({0,n-1});
	while(st.size()){
		int start=st.top().first;
		int end=st.top().second;
		st.pop();
		int val=vecArr[start];
		int left=start,right=end;
		while(left<right){
			while(right>left && vecArr[right]>=val){
				--right;
			}
			vecArr[left]=vecArr[right];
			while(left<right && vecArr[left]<=val){
				++left;
			}
			vecArr[right]=vecArr[left];
		}
		vecArr[left]=val;
		if(left-1>start){
			st.push({start,left-1});
		}
		if(left+1<end){
			st.push({left+1,end});
		}
	}
}
void Print(const vector<int>& vecArr){
	
	for(int i=0;i<vecArr.size();++i){
		cout<<vecArr[i]<<' ';
	}
	cout<<endl;
}
int main(){
	
	vector<int> vecArr({10,1,5,1,2,9,8,7});
	Print(vecArr);
	quilkSort(vecArr);
	Print(vecArr);
	return 0;
}
